/**
 *  @file AvlTree.cpp
 *
 *  Although coding of this AVL tree is not copied from the others,
 *  the algorithm is referenced from GNU libavl (http://www.stanford.edu/~blp/avl/). 
 */
#include "AvlTree.h"
#include "../../common/UtilFuncT.h"

namespace cppflib
{

namespace collections
{

namespace tree
{

AvlTree::AvlTree(void) : BinTree(true)
{
}

AvlTree::~AvlTree(void)
{
}


/**
 *  Though it accepts 'TreeNode', it must be an AvlTreeNode derived object
 */
bool AvlTree::Insert(TreeNode *pNode)
{
   bool isOK = true;

   do {

      if (!cppflib::InstanceOf<AvlTreeNode>(pNode)) {
         isOK = false;   // not an AvlTreeNode
         break;
      }

      AvlTreeNode *pNewNode = static_cast<AvlTreeNode*>(pNode);
      
      // normal insertion
      if (! (isOK = BinTree::Insert(pNewNode)))
         break;

      // update balance
      rotatetype_t rType = RT_NONE;
      AvlTreeNode *pUnbalancedNode = NULL;
      if ((rType = __UpdateBalanceInsert(pNewNode, &pUnbalancedNode)) == RT_NONE)
         break;

      // do rotation
      __RotateInsert(rType, pUnbalancedNode);
      
   } while(0);
   
   return isOK;
}

/**
 *  Delete a node
 *
 *  @note deletion, unlike insertion, require propagating the balance factor upward
 *        in some cases.
 */
bool AvlTree::Delete(const TreeNode &node)
{
   TreeNode *pDelParent = NULL;   
   AvlTreeNode *pUnbalancedNode = NULL;
   bool isOK = true;
   rotatetype_t rType;
   bool isLeftChild = false;

   do {
      if (! (isOK = BinTree::Delete(node, pDelParent, isLeftChild)))
         break;

      /*
       *  Unlike insertion, we may or may not need to propagate the balance info
       *  up the tree, which depends on the result from 
       *  "__UpdateBalanceDelete" and "__RotateDelete"
       */
      while (true) {
         // update balance factor
         if ((rType = __UpdateBalanceDelete(static_cast<AvlTreeNode*>(pDelParent), 
                                            isLeftChild, &pUnbalancedNode)) == RT_NONE)
            break;

         // do actual rebalancing by rotation
         pUnbalancedNode = __RotateDelete(rType, pUnbalancedNode);
         
         // No uppest node returned or root is reached
         if (!pUnbalancedNode || !pUnbalancedNode->m_pParent)
            break;

         // prepare for next round
         pDelParent = pUnbalancedNode->m_pParent;
         isLeftChild = (static_cast<AvlTreeNode*>(pDelParent)->m_leftChild == pUnbalancedNode);
         pUnbalancedNode = NULL;
      }

   } while(0);

   return isOK;
}

/**
 *   Do a Left-Right rotate and update balance factor as well.
 *
 *   pUnbalancedNode = y,
 *   pChild = x,
 *   pGrandChild = w
 *
 *        |                |                |   
 *    (--)y            (--)y             (0)w
 *       / \              / \              / \
 *   (+)x   d     =>  (?)w   d    =>  (?)x    y(?)
 *     / \              / \             / \  / \
 *    a   w(?)         x   c           a  b  c  d
 *       / \          / \
 *      b   c        a   b
 *
 *   if w is (0), a, b, c and d are null --> y and x are balanced
 *   if w is (-), a, b and d have height h > 0, c has height (h - 1)
 *        --> x is balanced, y is +1.
 *   if w is (+), a, c and d have height h > 0, b has height (h - 1)
 *        --> y is balanced, x is -1.
 *
 *  @return pointer to grand child
 */
AvlTreeNode * AvlTree::__LeftRight_Rotate(AvlTreeNode *pUnbalancedNode)
{
   AvlTreeNode *pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_leftChild);
   AvlTreeNode *pGrandChild = static_cast<AvlTreeNode*>(pChild->m_rightChild);
   
   this->LeftRotate(pChild);           // do a left rotate on left child
   this->RightRotate(pUnbalancedNode); // do a right rotate on unbalanced
   // update balance
   if (pGrandChild->bfactor == 0) {
      pUnbalancedNode->bfactor = 0;
      pChild->bfactor = 0;
   }
   else if (pGrandChild->bfactor == -1) {
      pUnbalancedNode->bfactor = 1;
      pChild->bfactor = 0;
   }
   else { // grand child is +1
      pUnbalancedNode->bfactor = 0;
      pChild->bfactor = -1;
   }

   // grand child should be 0 at the end
   pGrandChild->bfactor = 0;

   return pGrandChild;
}

/**
 *   Do a Right-Left rotate and update balance factor as well.
 *
 *   pUnbalancedNode = y,
 *   pChild = x,
 *   pGrandChild = w
 *
 *        |                |                |   
 *    (++)y            (++)y             (0)w
 *       / \              / \              / \
 *      d   x(-)  =>     d  w(?)  =>  (?)y    x(?)
 *         / \             / \          / \  / \
 *     (?)w   a           c   x(?)     d  c  b  a
 *       / \                 / \
 *      c   b               b   a
 *
 *   
 *   if w is (0), a, b, c and d are null --> y and x are balanced
 *   if w is (-), d, c and a have height h > 0, b has height (h - 1)
 *        --> y is balanced, x is +1.
 *   if w is (+), d, b and a have height h > 0, c has height (h - 1)
 *        --> x is balanced, y is -1.
 *
 *  @return pointer to grand child
 */
AvlTreeNode * AvlTree::__RightLeft_Rotate(AvlTreeNode *pUnbalancedNode)
{
   AvlTreeNode *pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_rightChild); 
   AvlTreeNode *pGrandChild = static_cast<AvlTreeNode*>(pChild->m_leftChild);

   this->RightRotate(pChild);         // do a right rotate on right child
   this->LeftRotate(pUnbalancedNode); // do a left rotate on unbalanced
   // update balance
   if (pGrandChild->bfactor == 0) {
      pUnbalancedNode->bfactor = 0;
      pChild->bfactor = 0;
   }
   else if (pGrandChild->bfactor == -1) {
      pUnbalancedNode->bfactor = 0;
      pChild->bfactor = 1;
   }
   else { // grand child is +1
      pUnbalancedNode->bfactor = -1;
      pChild->bfactor = 0;
   }

   // grand child should be 0 at the end
   pGrandChild->bfactor = 0;

   return pGrandChild;
}

/**
 *  Do rotation at the unbalanced node after insertion.
 *  Update balance factor as well.
 *
 *  @param [in] rType -- rotation type
 *  @param [in] pUnbalancedNode -- the node with +2 or -2
 *
 */
void AvlTree::__RotateInsert(rotatetype_t rType, AvlTreeNode *pUnbalancedNode)
{
    AvlTreeNode *pChild = NULL;

    switch (rType) {
       /*
        *   pUnbalancedNode = y,
        *   pChild = x
        *
        *        |                |             |   
        *     (-)y            (--)y          (0)x
        *       / \              / \           / \
        *   (0)x   c   =>    (-)x   c   =>   *a   y(0)
        *     / \              / \               / \
        *    a   b           *a   b             b   c
        *
        *   left of y decrease by 1 --> y is balanced
        *   left of x increase by 1, right of x increase by 1 --> x is balanced
        */
       case RT_LL: 
          pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_leftChild);
          this->RightRotate(pUnbalancedNode);
          // update balance, just leave grandchild unchanged
          pUnbalancedNode->bfactor = 0;
          pChild->bfactor = 0;
          break;
       /*
        *   pUnbalancedNode = y,
        *   pChild = x
        *
        *        |                |               |   
        *     (+)y            (++)y            (0)x
        *       / \              / \             / \
        *      c   x(0) =>      c   x(+) =>  (0)y   b*  
        *         / \              / \         / \
        *        a   b            a   b*      c   a
        *
        *   right of y decrease by 1 --> y is balanced
        *   right of x increase by 1, left of x increase by 1 --> x is balanced
        */
       case RT_RR: 
          pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_rightChild);
          this->LeftRotate(pUnbalancedNode);
          // update balance, just leave grandchild unchanged
          pUnbalancedNode->bfactor = 0;
          pChild->bfactor = 0;
          break;
       /*
        *  Right-Left rotate
        */
       case RT_RL: 
          __RightLeft_Rotate(pUnbalancedNode);
          break;
       /*
        *  Left-Rigth rotate
        */
       case RT_LR: 
          __LeftRight_Rotate(pUnbalancedNode);
          break;
       default:
          break;
    } // end of switch

}

/**
 *  Update balance factor after insertion.
 *
 *  Propagate balance factor upward until 
 *  1) root is reached,
 *  2) a node with +2 or -2 is reached or
 *  3) a node with 0 (after updating) is reached (no rotation required)
 *  
 *  @param [in] pNode -- newly added node
 *  @param [out] pUnbalancedNode -- the node with +2 or -2
 *
 *  @return type of rotation required
 */
AvlTree::rotatetype_t AvlTree::__UpdateBalanceInsert(AvlTreeNode *pNode, AvlTreeNode **pUnbalancedNode)
{
    AvlTreeNode *pParent;
    rotatetype_t rType = RT_NONE;

    while ((pParent = static_cast<AvlTreeNode*>(pNode->m_pParent))) {
       
       pParent->bfactor += (pParent->m_leftChild == pNode) ? -1 : 1;
       int parentFactor = pParent->bfactor;

       // a balanced tree !
       if (parentFactor == 0)
          break;

       if (parentFactor >= 2 || parentFactor <= -2) {
          int nodeFactor = pNode->bfactor;

          // determine rotation type
          if (parentFactor == 2 && nodeFactor == 1) rType = RT_RR;
          else if (parentFactor == 2 && nodeFactor == -1) rType = RT_RL;
          else if (parentFactor == -2 && nodeFactor == 1) rType = RT_LR;
          else if (parentFactor == -2 && nodeFactor == -1) rType = RT_LL;

          // return this node
          *pUnbalancedNode = pParent;
          break;
       }

       pNode = pParent; // move upward
    }

    return rType;
}

/**
 *  Do rotation at the unbalanced node after deletion.
 *  Update balance factor as well.
 *
 *  @param [in] rType -- rotation type
 *  @param [in] pUnbalancedNode -- the node with +2 or -2
 *
 *  @return the "uppest" node after rebalancing or NULL if no need to propagage 
 *          balance info upward any more.
 */
AvlTreeNode * AvlTree::__RotateDelete(rotatetype_t rType, AvlTreeNode *pUnbalancedNode)
{
    AvlTreeNode *pChild, *pUppestNode = NULL;

    switch (rType) {
       /*
        *  Left-Left rotate
        *
        *   pUnbalancedNode = y,
        *   pChild = x
        *
        *   case I (tree can reveal the change after rotation, no need to propagate upward):
        *        |             |   
        *    (--)y          (+)x
        *       / \           / \
        *   (0)x   c*  =>   a   y(-)
        *     / \               / \
        *    a  b              b   c*
        *
        *   left of y decrease by 1 --> y is (-)
        *   right of x increase by 1 --> x is (+)
        *
        *   case II (tree can't reveal the change after rotation, propagate upward):
        *        |             |   
        *    (--)y          (0)x
        *       / \           / \
        *   (-)x   c  =>    *a   y(0)
        *     / \               / \
        *   *a  b              b   c
        *
        *   left of y decrease by 1 --> y is balanced
        *   left of x increase by 1, right of x increase by 1 --> x is balanced
        */
       case RT_LL: 
          pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_leftChild);
          this->RightRotate(pUnbalancedNode);
          // update balance, just leave grandchild unchanged

          if (pChild->bfactor == 0) {
             // case I
             pUnbalancedNode->bfactor = -1;
             pChild->bfactor = 1;
             // no uppest node return, stop loop
          }
          else {
             // case II
             pUnbalancedNode->bfactor = 0;
             pChild->bfactor = 0;
             pUppestNode = pChild;
          }
          break;
       /*
        *  Right-Right rotate
        *
        *   pUnbalancedNode = y,
        *   pChild = x
        *
        *   case I (tree can reveal the change after rotation, no need to propagate upward):
        *        |                |   
        *    (++)y             (-)x
        *       / \              / \
        *     *c  x(0)  =>   (+)y   b
        *        / \           / \
        *       a  b         *c  a
        *
        *   right of y decrease by 1 --> y is (+)
        *   left of x increase by 1 --> x is (-)
        *
        *   case II (tree can't reveal the change after rotation, propagate upward):
        *        |                |   
        *    (++)y             (0)x
        *       / \              / \
        *      c  x(+)  =>   (0)y   b*  
        *        / \           / \
        *       a  b*         c  a
        *
        *   right of y decrease by 1 --> y is balanced
        *   right of x increase by 1, left of x increase by 1 --> x is balanced
        */
       case RT_RR: 
          pChild = static_cast<AvlTreeNode*>(pUnbalancedNode->m_rightChild);
          this->LeftRotate(pUnbalancedNode);
          // update balance, just leave grandchild unchanged

          if (pChild->bfactor == 0) {
             // case I
             pUnbalancedNode->bfactor = 1;
             pChild->bfactor = -1;
             // no uppest node return, stop loop
          }
          else {
              // case II
             pUnbalancedNode->bfactor = 0;
             pChild->bfactor = 0;
             pUppestNode = pChild;
          }
          break;
       /*
        *  Right-Left rotate
        */
       case RT_RL: 
          pUppestNode = __RightLeft_Rotate(pUnbalancedNode);
          break;
       /*
        *  Left-Rigth rotate
        */
       case RT_LR: 
          pUppestNode = __LeftRight_Rotate(pUnbalancedNode);
          break;
       default:
          break;
    } // end of switch

    return pUppestNode;
}

/**
 *  Update balance factor after deletion.
 *
 *  Propagate balance factor upward until 
 *  1) root is reached,
 *  2) a node with +2 or -2 is reached (do rebalance) or
 *  3) a node with 0 (before updating) is reached (no rotation required)
 *  
 *  @param [in] pPrevParent -- previous node's parent (may be NULL)
 *  @param [in] isLeftChild -- TRUE: previous node is a left child.
 *                             FALSE: previous node is a right child.
 *  @param [out] pUnbalancedNode -- the node with +2 or -2
 *
 *  @return type of rotation required
 */
AvlTree::rotatetype_t AvlTree::__UpdateBalanceDelete(AvlTreeNode *pPrevParent, bool isLeftChild, AvlTreeNode **pUnbalancedNode)
{
    AvlTreeNode *pNode = pPrevParent;
    rotatetype_t rType = RT_NONE;

    while (pNode) {

       int nodeFactor = pNode->bfactor;
       pNode->bfactor += (isLeftChild) ? 1 : -1;

       if (nodeFactor == 0) {
          // original 0 --> +1 or -1
          break;  // no need to do rebalancing, since overall tree height has no change
       }
       else {
          nodeFactor = pNode->bfactor;
          if (nodeFactor >= 2 || nodeFactor <= -2) {
             //  original +1 --> +2 or
             //  original -1 --> -2
             int childFactor = (nodeFactor >= 2) ? static_cast<AvlTreeNode*>(pNode->m_rightChild)->bfactor :
                                                   static_cast<AvlTreeNode*>(pNode->m_leftChild)->bfactor;
             // determine rotation type
             if (nodeFactor == 2 && (childFactor == 1 || childFactor == 0)) rType = RT_RR;
             else if (nodeFactor == 2 && childFactor == -1) rType = RT_RL;
             else if (nodeFactor == -2 && childFactor == 1) rType = RT_LR;
             else if (nodeFactor == -2 && (childFactor == -1 || childFactor == 0)) rType = RT_LL;

             // return this node
             *pUnbalancedNode = pNode;
             break; // break to do rebalance, come back to this function later if necessary
          }
          else {
             // original +1 or -1 --> 0
             // move upward to update balance factor

             // update for next round
             if (pNode->m_pParent) {
                isLeftChild = (static_cast<AvlTreeNode*>(pNode->m_pParent)->m_leftChild == pNode);
             }
             pNode = static_cast<AvlTreeNode*>(pNode->m_pParent); // parent may be NULL
          }
       }
       
    } // end of while

    return rType;
}


}  // end of namespace tree

}  // end of namespace collections

}  // end of namespace cppflib

